#ifndef HASH_H
#define HASH_H
#include <iostream>
using std::cout;
using std::endl;


template <class Key,class Value> class htable{
public:
	class entry{
		friend class htable<Key, Value>;
		Key key;
		Value val;
		int hash;
		entry* next;
		entry* listcopy(entry* src){
			if(src == 0)
				return 0;
			entry* ret = new entry(src->key,src->val,listcopy(src->next));
			return ret;
		}
	public:
		entry():key(),val(),hash(0),next(0){}
		entry(const Key& k, const Value& v, entry* nxt=0):key(k),val(v),hash(0),next(nxt){}
		entry(const entry& x):key(x.key),val(x.val),hash(x.hash),next(x.next){}
		entry& operator=(const entry& x){
			if(this==&x)
				return *this;
			delete next;
			key = x.key;
			val = x.val;
			hash = x.hash;
			next = listcopy(x.next);		
		}
		~entry(){
			delete next;
		}
		Key getKey(){
			return key;
		}
		Value getValue(){
			return val;
		}
	};
private:
	entry* table;
	int capacity;
	int count;
	int threshold;
	float loadFactor;
	void rehash(){
		int oldCapacity = capacity;
		entry* oldTable = table;

		capacity = oldCapacity * 2 + 1;
		table = new entry[capacity];

		threshold = (int)(capacity * loadFactor);

		for (int i = oldCapacity ; i-- > 0 ;) {
			for (entry* old = oldTable[i].next ; old != 0 ; old = old->next) {
				entry* e = new entry(*old);
				int index = (e->hash & 0x7FFFFFFF) % capacity;
				e->next = table[index].next;
				table[index].next = e;
			}
		}
		delete[] oldTable;
	}
public:
	htable(int initial=101, float load=0.75):table(new entry[initial]), capacity(initial), count(0), threshold((int)(initial*load)), loadFactor(load){}
	virtual ~htable(){
		delete[] table;
	}
	htable(const htable& H){
		capacity = H.capacity;
		count = H.count;
		threshold = H.threshold;
		loadFactor = H.loadFactor;
		table = new entry[capacity];
		for(int i=0; i<capacity; i++){
			table[i] = H.table[i];
		}
	}

	htable& operator=(const htable& H){
		if(this == &H)
			return *this;
		delete[] table;
		capacity = H.capacity;
		count = H.count;
		threshold = H.threshold;
		loadFactor = H.loadFactor; 
		table = new entry[capacity];
		for(int i=0; i<capacity; i++){
			table[i] = H.table[i];
		}
		return *this;
	}

	entry* get(const Key& k)const{
		entry* ret;
		int hash = hashfunc(k);
		int index = (hash & 0x7FFFFFFF) % capacity;
		for(ret=table[index].next; ret!=0; ret=ret->next){
			if(k == ret->key)
				return ret;
		}
		return ret;
	}

	void put(const Key& k, const Value& v){
		entry* e;
		int hash = hashfunc(k);
		int index = (hash & 0x7FFFFFFF) % capacity;
		for(e=table[index].next; e!=0; e=e->next){
			if(k == e->key){
				e->val = v;
				return;
			}
		}
		if(e==0){
			e = new entry(k,v,table[index].next);
			e->hash = hashfunc(k);
			table[index].next = e;
		}	
		count++;
		if(count>threshold)
			rehash();
	}
	void dump(){
		for(int i=capacity; i-- > 0;){
			for(entry* e=table[i].next; e!=0; e=e->next){
				cout << e->getKey() <<" -> "<< e->getValue() << endl;
			}
		}
	}

	virtual int hashfunc(const Key&)const=0;
};


#endif
